前置知识
- 动态规划
- 括号表示法（或最小表示法）
- 状态压缩
- 哈希表
一些定义
先看模板题：P5056@洛谷 - 【模板】插头dp
插头 dp 主要用于解决网格图上的哈密顿回路相关的问题。
插头
插头就是网格图上一个格子与另一个格子相连的位置，如图。
轮廓线
在我们指定一个当前格子时，他的下侧和右侧连接到边界的线成为轮廓线。
如图，蓝色格子为当前格子，红色线为轮廓线。
毒瘤动规 - 插头 dp
设计状态
插头 dp 中状态为一条轮廓线，每次状态转移转移一个格子，轮廓线转移如图：
状态压缩
由于数据量太大，这里需要使用状态压缩。
我们知道，为了形成回路，在任意时刻插头均不会相交。（红色为插头，绿色为轮廓线）
于是想到括号串。这里我们用 、、 来表示轮廓线为在左侧的插头、在右侧的插头或没有插头。
因为需要状态压缩，我们考虑使用括号表示法（最小表示法也可以，但在本文中不会涉及）。在这里我们将 分别表示空插头、左侧插头和右侧插头。
状态转移
状态转移有如下几种情况：
当前格为障碍
若当前格为障碍，直接转移即可。
当前格既没有上插头又没有左插头
此时为了满足经过所有格子，添加右侧和下侧的插头，即在括号串中将一对 替换为 。
当前格有上插头
则有两种转移方式——直走延长插头或转弯。
当前格有左插头
同理。
当前格既有上插头又有左插头
均为 或均为
此时将两个 （）合并变为 ，并向右侧（左侧）找到第一个右插头（左插头）变为左插头（右插头）。
左插头为 、上插头为
此时直接连起来即可。
左插头为 、上插头为
此时将要形成闭合回路。判断当前格是否为最后一格，是则连接并更新答案，否则状态不合法。
其他细节
我们建立滚动哈希表方便压缩空间，同时 dp 只记录哈希位置的值。因为是哈希表，因此在每一行开始的时候都需要 modifyQue() 来滚动、更换值。
完整代码
您大可先看看我 23 次才 AC 的提交记录。
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
#define fil(a,b) memset((a),(b),sizeof(a))
#define in inline
using namespace std;
typedef long long ll;
const ll N = 12+5, X = 3e5+5, K = 1<<25|5, mod = 299987;
ll n, m, dx, dy, bit, lst, ans;
ll a[N][N], p[N], h[X], nxt[K], que[2][K], val[2][K], cnt[2];
in void add(ll hash, ll status, ll tot) {
nxt[++cnt[bit]] = h[hash];
h[hash] = cnt[bit];
que[bit][cnt[bit]] = status;
val[bit][cnt[bit]] = tot;
}
in void insert(ll status, ll tot) {
int hash = status % mod + 1;
for(ll i=h[hash];i;i=nxt[i]) {
if(que[bit][i] == status) {
val[bit][i] += tot;
return;
}
}
add(hash, status, tot);
}
in void modifyQue() {
for(ll i=1;i<=cnt[bit];i++) {
que[bit][i] <<= 2;
}
}
in void dp() {
cnt[bit] = 1;
val[bit][1] = 1;
que[bit][1] = 0;
for(ll i=1;i<=n;i++) {
modifyQue();
for(ll j=1;j<=m;j++) {
fil(h, 0);
lst = bit;
bit ^= 1;
cnt[bit] = 0;
for(ll k=1;k<=cnt[lst];k++) {
ll status = que[lst][k];
ll tot = val[lst][k];
ll P1 = (status >> ((j - 1) * 2)) % 4;
ll P2 = (status >> (j * 2)) % 4;
if(!a[i][j]) {
if(!P1 && !P2) {
insert(status, tot);
}
}
else if(!P1 && !P2) {
if(a[i][j+1] && a[i+1][j]) {
ll nxtStatus = status + p[j-1] + 2 * p[j];
insert(nxtStatus, tot);
}
}
else if(!P1 && P2) {
if(a[i][j+1]) {
insert(status, tot);
}
if(a[i+1][j]) {
ll nxtStatus = status - p[j] * P2 + p[j-1] * P2;
insert(nxtStatus, tot);
}
}
else if(P1 && !P2) {
if(a[i+1][j]) {
insert(status, tot);
}
if(a[i][j+1]) {
ll nxtStatus = status - p[j-1] * P1 + p[j] * P1;
insert(nxtStatus, tot);
}
}
else if(P1 == 1 && P2 == 1) {
ll tmp = 1;
for(ll l=j+1;l<=m;l++) {
ll Pid = (status >> (l * 2)) % 4;
if(Pid == 1) {
++tmp;
}
else if(Pid == 2) {
--tmp;
}
if(!tmp) {
ll nxtStatus = status - p[j] - p[j-1] - p[l];
insert(nxtStatus, tot);
break;
}
}
}
else if(P1 == 2 && P2 == 2) {
ll tmp = 1;
for(ll l=j-2;l>=0;l--) {
ll Pid = (status >> (l << 1)) % 4;
if(Pid == 1) {
--tmp;
}
else if(Pid == 2) {
++tmp;
}
if(!tmp) {
ll nxtStatus = status - 2 * p[j] - 2 * p[j-1] + p[l];
insert(nxtStatus, tot);
break;
}
}
}
else if(P1 == 2 && P2 == 1) {
ll nxtStatus = status - 2 * p[j-1] - p[j];
insert(nxtStatus, tot);
}
else if(i == dx && j == dy) {
ans += tot;
}
}
}
}
}
int main() {
scanf("%lld%lld", &n, &m);
for(ll i=1;i<=n;i++) {
string s;
cin>>s;
s = ' ' + s;
for(ll j=1;j<=m;j++) {
if(s[j] == '.') {
a[i][j] = 1;
dx = i;
dy = j;
}
}
}
p[0] = 1;
for(ll i=1;i<=12;i++) {
p[i] = p[i-1] << 2;
}
dp();
printf("%lld\n", ans);
return 0;
}